Package edu.claflin.finder.algo

Class MatrixPatternAnalyzer

java.lang.Object
edu.claflin.finder.algo.Algorithm
edu.claflin.finder.algo.MatrixPatternAnalyzer
All Implemented Interfaces:
Processable<Graph,Graph>
@Deprecated public class MatrixPatternAnalyzer extends Algorithm
Deprecated.
No replacement yet. Inefficient and utilizes old algorithm strategy.
Processes a Graph searching for bipartite subgraphs by analyzing the matrices of said Graph.
Version:
3.0.2 February 4, 2016
Author:
Charles Allen Schultz II

  • Constructor Details

    • MatrixPatternAnalyzer

      public MatrixPatternAnalyzer()
      Deprecated.
      Public constructor for initializing the analyzer. Currently ignores state variables given it doesn't operate on an expansion basis.

  • Method Details

    • process

      public ArrayList<Graph> process(Graph graph)
      Deprecated.
      Processes data.

      Processes the Graph object in four steps.
      1) Check for valid 0 Sub-matrices.
      2) Iterate on Step 1 through all contiguous node groupings.
      3) Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
      4) Repeat Step 3 for each transposition of the Graph. Each step is carried out in its own method. This method controls Step 4 by looping through all the permutations of the supplied Graph object. The permutation code is based on the "Counting QuickPerm Algorithm" found here:
      Parameters:
      graph - the Graph object to search for Bipartite subgraphs.
      Returns:
      the ArrayList of Graph objects containing found bipartite subgraph objects.

    • checkSubGraphs

      private Graph checkSubGraphs(Graph inGraph, int transpositions)
      Deprecated.
      Step 3: Repeat Step 2 for each "Cornered" Sub-matrix of the original Graph.
      A "Cornered" sub-matrix is a sub-matrix whose upper left node lies in the upper left corner of the main matrix. I.e. A(0,0) = B(0,0) if A is the main matrix and B is the sub-matrix.
      This method processes Step 2 with each of the n - 1 cornered matrices contained in the original matrix. The smallest cornered matrix containing only one node is not processed (due to it being impossible to sort one node into two disjoint sets.
      Parameters:
      inGraph - the graph
      transpositions - the number of transpositions
      Returns:
      result of step 3

    • checkNodeGroupings

      private boolean checkNodeGroupings(Graph inGraph)
      Deprecated.
      Step 2: Iterate on Step 1 through all contiguous node groupings. Bipartite graphs may have a ratio of m:n nodes in each disjoint set. Since both node counts are independent of each other, all possible options (except cases where m or n = 0) must be checked.
      This section of the algorithm instructs the previous to examine a very specific section of the subgraphs for contiguous zeroes. It iterates through all valid contiguous groupings.
      Parameters:
      inGraph - the (sub) Graph object to check for bipartiteness.
      Returns:
      the boolean primitive indicating if the Graph was bipartite.

    • checkZeroMatrices

      private boolean checkZeroMatrices(Graph inGraph, int nodeCap)
      Deprecated.
      Step 1: Check for valid 0 Sub-matrices.
      Undirected bipartite graphs, when ordered correctly, have two noticeable regions containing no edges, or, if the graph is represented by ones and zeroes, two regions of zeros. The following graph demonstrates this.

       [ 0 0 0 0 1 ]
      
 [ 0 0 0 1 1 ]
      
 [ 0 0 0 1 0 ]
      
 [ 0 1 1 0 0 ]
      
 [ 1 1 0 0 0 ]
      This section of the code verifies that these contiguous regions exist. If they don't, the provided Graph object (or subgraph object in this case) is not Bipartite. This is the core comparison to be performed.
      Parameters:
      inGraph - the Graph object to check for valid 0 sub-matrices.
      nodeCap - the furthest node inward which the upperLeft Matrix should extend to.
      Returns:
      the boolean primitive indicating if the sub-matrix is bipartite.